package com.cat.graphTheory;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/
 * @create 2025/10/5 22:07
 * @since JDK17
 */

public class Solution37 {
    int N = ((int) (1e9 + 7));
    long deal(int n) {
        long ans = 1, x = 3;
        while (n > 0) {
            if ((n & 1) != 0) {
                ans = (ans * x) % N;
            }
            x = (x * x) % N;
            n >>= 1;
        }
        return ans;
    }

    public int cuttingBamboo(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }

        int tail = n % 3 == 0 ? 1 : (n % 3 == 1 ? 4 : 2);
        int p = (tail == 1 ? n : (n - tail)) / 3;
        return (int)((tail * deal(p)) % N);
    }
}
